home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1993 / Internet Info CD-ROM (Walnut Creek) (1993).iso / networking / ip / ka9q / aztecnos.arc / IPROUTE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1989-03-19  |  14.3 KB  |  586 lines
  1. /* Lower half of IP, consisting of gateway routines
  2.  * Includes routing and options processing code
  3.  */
  4. #include "global.h"
  5. #include "mbuf.h"
  6. #include "internet.h"
  7. #include "timer.h"
  8. #include "netuser.h"
  9. #include "ip.h"
  10. #include "icmp.h"
  11. #include "iface.h"
  12. #include "trace.h"
  13.  
  14. int16 lcsum();
  15. static int16 hash_ip();
  16. static struct route *rt_lookup();
  17.  
  18. struct route *Routes[32][NROUTE];    /* Routing table */
  19. struct route R_default;            /* Default route entry */
  20.  
  21. int32 Ip_addr;
  22. struct ip_stats Ip_stats;
  23.  
  24. /* Route an IP datagram. This is the "hopper" through which all IP datagrams,
  25.  * coming or going, must pass.
  26.  *
  27.  * "rxbroadcast" is set to indicate that the packet came in on a subnet
  28.  * broadcast. The router will kick the packet upstairs regardless of the
  29.  * IP destination address.
  30.  */
  31. int
  32. ip_route(bp,rxbroadcast)
  33. struct mbuf *bp;
  34. int rxbroadcast;    /* True if packet had link broadcast address */
  35. {
  36.     struct ip ip;            /* IP header being processed */
  37.     int16 ip_len;            /* IP header length */
  38.     int16 length;            /* Length of data portion */
  39.     int32 gateway;            /* Gateway IP address */
  40.     register struct route *rp;    /* Route table entry */
  41.     struct iface *iface;        /* Output interface, possibly forwarded */
  42.     int16 offset;            /* Offset into current fragment */
  43.     int16 mf_flag;            /* Original datagram MF flag */
  44.     int strict = 0;            /* Strict source routing flag */
  45.     char prec;            /* Extracted from tos field */
  46.     char del;
  47.     char tput;
  48.     char rel;
  49.     int16 opt_len;        /* Length of current option */
  50.     char *opt;        /* -> beginning of current option */
  51.     char *ptr;        /* -> pointer field in source route fields */
  52.     struct mbuf *tbp;
  53.  
  54.     Ip_stats.total++;
  55.     if(len_mbuf(bp) < IPLEN){
  56.         /* The packet is shorter than a legal IP header */
  57.         Ip_stats.runt++;
  58.         free_p(bp);
  59.         return -1;
  60.     }
  61.     /* Sneak a peek at the IP header's IHL field to find its length */
  62.     ip_len = (bp->data[0] & 0xf) << 2;
  63.     if(ip_len < IPLEN){
  64.         /* The IP header length field is too small */
  65.         Ip_stats.length++;
  66.         free_p(bp);
  67.         return -1;
  68.     }
  69.     if(cksum(NULLHEADER,bp,ip_len) != 0){
  70.         /* Bad IP header checksum; discard */
  71.         Ip_stats.checksum++;
  72.         free_p(bp);
  73.         return -1;
  74.     }
  75.     /* Extract IP header */
  76.     ntohip(&ip,&bp);
  77.  
  78.     if(ip.version != IPVERSION){
  79.         /* We can't handle this version of IP */
  80.         Ip_stats.version++;
  81.         free_p(bp);
  82.         return -1;
  83.     }
  84.     /* Trim data segment if necessary. */
  85.     length = ip.length - ip_len;    /* Length of data portion */
  86.     trim_mbuf(&bp,length);    
  87.                 
  88.     /* Process options, if any. Also compute length of secondary IP
  89.      * header in case fragmentation is needed later
  90.      */
  91.     strict = 0;
  92.     for(opt = ip.options; opt < &ip.options[ip.optlen];opt += opt_len){
  93.         /* Most options have a length field. If this is a EOL or NOOP,
  94.          * this (garbage) value won't be used
  95.          */
  96.         opt_len = uchar(opt[1]);
  97.  
  98.         switch(opt[0] & OPT_NUMBER){
  99.         case IP_EOL:
  100.             goto no_opt;    /* End of options list, we're done */
  101.         case IP_NOOP:
  102.             opt_len = 1;
  103.             break;        /* No operation, skip to next option */
  104.         case IP_SSROUTE:    /* Strict source route & record route */
  105.             strict = 1;    /* note fall-thru */
  106.         case IP_LSROUTE:    /* Loose source route & record route */
  107.             /* Source routes are ignored unless we're in the
  108.              * destination field
  109.              */
  110.             if(ip.dest != Ip_addr)
  111.                 break;    /* Skip to next option */
  112.             if(uchar(opt[2]) >= opt_len){
  113.                 break;    /* Route exhausted; it's for us */
  114.             }
  115.             /* Put address for next hop into destination field,
  116.              * put our address into the route field, and bump
  117.              * the pointer
  118.              */
  119.             ptr = opt + uchar(opt[2]) - 1;
  120.             ip.dest = get32(ptr);
  121.             put32(ptr,Ip_addr);
  122.             opt[2] += 4;
  123.             break;
  124.         case IP_RROUTE:    /* Record route */
  125.             if(uchar(opt[2]) >= opt_len){
  126.                 /* Route area exhausted; kick back an error */
  127.                 union icmp_args icmp_args;
  128.  
  129.                 icmp_args.pointer = IPLEN + opt - ip.options;
  130.                 icmp_output(&ip,bp,PARAM_PROB,0,&icmp_args);
  131.                 free_p(bp);
  132.                 return -1;
  133.             }
  134.             /* Add our address to the route */
  135.             ptr = opt + uchar(opt[2]) - 1;
  136.             ptr = put32(ptr,Ip_addr);
  137.             opt[2] += 4;
  138.             break;
  139.         }
  140.     }
  141. no_opt:
  142.  
  143.     /* See if it's a broadcast or addressed to us, and kick it upstairs */
  144.     if(ip.dest == Ip_addr || rxbroadcast){
  145. #ifdef    GWONLY
  146.     /* We're only a gateway, we have no host level protocols */
  147.         if(!rxbroadcast)
  148.             icmp_output(&ip,bp,DEST_UNREACH,PROT_UNREACH,(union icmp_args *)NULL);
  149.         free_p(bp);
  150. #else
  151.         ip_recv(&ip,bp,rxbroadcast);
  152. #endif
  153.         return 0;
  154.     }
  155.     /* Decrement TTL and discard if zero */
  156.     if(--ip.ttl == 0){
  157.         /* Send ICMP "Time Exceeded" message */
  158.         icmp_output(&ip,bp,TIME_EXCEED,0,NULLICMP);
  159.         free_p(bp);
  160.         return -1;
  161.     }
  162.     /* Look up target address in routing table */
  163.     if((rp = rt_lookup(ip.dest)) == NULLROUTE){
  164.         /* No route exists, return unreachable message */
  165.         icmp_output(&ip,bp,DEST_UNREACH,HOST_UNREACH,NULLICMP);
  166.         free_p(bp);
  167.         return -1;
  168.     }
  169.     /* Check for output forwarding and divert if necessary */
  170.     iface = rp->iface;
  171.     if(iface->forw != NULLIF)
  172.         iface = iface->forw;
  173.  
  174.     /* Find gateway; zero gateway in routing table means "send direct" */
  175.     if(rp->gateway == (int32)0)
  176.         gateway = ip.dest;
  177.     else
  178.         gateway = rp->gateway;
  179.  
  180.     if(strict && gateway != ip.dest){
  181.         /* Strict source routing requires a direct entry */
  182.         icmp_output(&ip,bp,DEST_UNREACH,ROUTE_FAIL,NULLICMP);
  183.         free_p(bp);
  184.         return -1;
  185.     }
  186.     prec = PREC(ip.tos);
  187.     del = ip.tos & DELAY;
  188.     tput = ip.tos & THRUPUT;
  189.     rel = ip.tos & RELIABILITY;
  190.  
  191.     if(ip.length <= iface->mtu){
  192.         /* Datagram smaller than interface MTU; put header
  193.          * back on and send normally
  194.          */
  195.         if((tbp = htonip(&ip,bp)) == NULLBUF){
  196.             free_p(bp);
  197.             return -1;
  198.         }
  199.         return (*iface->send)(tbp,iface,gateway,prec,del,tput,rel);
  200.     }
  201.     /* Fragmentation needed */
  202.     if(ip.flags.df){
  203.         /* Don't Fragment set; return ICMP message and drop */
  204.         icmp_output(&ip,bp,DEST_UNREACH,FRAG_NEEDED,NULLICMP);
  205.         free_p(bp);
  206.         return -1;
  207.     }
  208.     /* Create fragments */
  209.     offset = ip.offset;
  210.     mf_flag = ip.flags.mf;        /* Save original MF flag */
  211.     while(length != 0){        /* As long as there's data left */
  212.         int16 fragsize;        /* Size of this fragment's data */
  213.         struct mbuf *f_data;    /* Data portion of fragment */
  214.  
  215.         /* After the first fragment, should remove those
  216.          * options that aren't supposed to be copied on fragmentation
  217.          */
  218.         ip.offset = offset;
  219.         if(length + ip_len <= iface->mtu){
  220.             /* Last fragment; send all that remains */
  221.             fragsize = length;
  222.             ip.flags.mf = mf_flag;    /* Pass original MF flag */
  223.         } else {
  224.             /* More to come, so send multiple of 8 bytes */
  225.             fragsize = (iface->mtu - ip_len) & 0xfff8;
  226.             ip.flags.mf = 1;
  227.         }
  228.         ip.length = fragsize + ip_len;
  229.  
  230.         /* Move the data fragment into a new, separate mbuf */
  231.         if((f_data = alloc_mbuf(fragsize)) == NULLBUF){
  232.             free_p(bp);
  233.             return -1;
  234.         }
  235.         f_data->cnt = pullup(&bp,f_data->data,fragsize);
  236.  
  237.         /* Put IP header back on */
  238.         if((tbp = htonip(&ip,f_data)) == NULLBUF){
  239.             free_p(f_data);
  240.             free_p(bp);
  241.             return -1;
  242.         }
  243.         /* and ship it out */
  244.         if((*iface->send)(tbp,iface,gateway,prec,del,tput,rel) == -1)
  245.             return -1;
  246.  
  247.         offset += fragsize;
  248.         length -= fragsize;
  249.     }
  250.     return 0;
  251. }
  252.  
  253. struct rt_cache Rt_cache;
  254.  
  255. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  256. int
  257. rt_add(target,bits,gateway,iface)
  258. int32 target;        /* Target IP address prefix */
  259. unsigned int bits;    /* Size of target address prefix in bits (0-32) */
  260. int32 gateway;
  261. struct iface *iface;
  262. {
  263.     struct route *rp,**hp;
  264.     int16 i;
  265.     int32 mask;
  266.  
  267.     if(iface == NULLIF)
  268.         return -1;
  269.  
  270.     Rt_cache.target = 0;    /* Flush cache */
  271.  
  272.     /* Zero bits refers to the default route */
  273.     if(bits == 0){
  274.         rp = &R_default;
  275.     } else {
  276.         if(bits > 32)
  277.             bits = 32;
  278.  
  279.         /* Mask off don't-care bits */
  280.         mask = 0xffffffff;
  281.         for(i=31;i >= bits;i--)
  282.             mask <<= 1;
  283.  
  284.         target &= mask;
  285.         /* Search appropriate chain for existing entry */
  286.         for(rp = Routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  287.             if(rp->target == target)
  288.                 break;
  289.         }
  290.     }
  291.     if(rp == NULLROUTE){
  292.         /* The target is not already in the table, so create a new
  293.          * entry and put it in.
  294.          */
  295.         if((rp = (struct route *)malloc(sizeof(struct route))) == NULLROUTE)
  296.             return -1;    /* No space */
  297.         /* Insert at head of table */
  298.         rp->prev = NULLROUTE;
  299.         hp = &Routes[bits-1][hash_ip(target)];
  300.         rp->next = *hp;
  301.         if(rp->next != NULLROUTE)
  302.             rp->next->prev = rp;
  303.         *hp = rp;
  304.     }
  305.     rp->target = target;
  306.     rp->gateway = gateway;
  307.     rp->iface = iface;
  308.  
  309.     return 0;
  310. }
  311.  
  312. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  313.  * if entry was not in table.
  314.  */
  315. int
  316. rt_drop(target,bits)
  317. int32 target;
  318. unsigned int bits;
  319. {
  320.     register struct route *rp;
  321.     unsigned int i;
  322.     int32 mask;
  323.  
  324.     Rt_cache.target = 0;    /* Flush the cache */
  325.  
  326.     if(bits == 0){
  327.         /* Nail the default entry */
  328.         R_default.iface = NULLIF;
  329.         return 0;
  330.     }
  331.     if(bits > 32)
  332.         bits = 32;
  333.  
  334.     /* Mask off don't-care bits */
  335.     mask = 0xffffffff;
  336.     for(i=31;i >= bits;i--)
  337.         mask <<= 1;
  338.  
  339.     target &= mask;
  340.  
  341.     /* Search appropriate chain for existing entry */
  342.     for(rp = Routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  343.         if(rp->target == target)
  344.             break;
  345.     }
  346.     if(rp == NULLROUTE)
  347.         return -1;    /* Not in table */
  348.  
  349.     if(rp->next != NULLROUTE)
  350.         rp->next->prev = rp->prev;
  351.     if(rp->prev != NULLROUTE)
  352.         rp->prev->next = rp->next;
  353.     else
  354.         Routes[bits-1][hash_ip(target)] = rp->next;
  355.  
  356.     free((char *)rp);
  357.     return 0;
  358. }
  359.  
  360. /* Compute hash function on IP address */
  361. static int16
  362. hash_ip(addr)
  363. register int32 addr;
  364. {
  365.     register unsigned int ret;
  366.  
  367.     ret = hiword(addr);
  368.     ret ^= loword(addr);
  369.     return ret % NROUTE;
  370. }
  371. #ifndef    GWONLY
  372. /* Given an IP address, return the MTU of the local interface used to
  373.  * reach that destination. This is used by TCP to avoid local fragmentation
  374.  */
  375. int16
  376. ip_mtu(addr)
  377. int32 addr;
  378. {
  379.     register struct route *rp;
  380.     struct iface *iface;
  381.  
  382.     rp = rt_lookup(addr);
  383.     if(rp == NULLROUTE || rp->iface == NULLIF)
  384.         return 0;
  385.  
  386.     iface = rp->iface;
  387.     if(iface->forw != NULLIF)
  388.         return iface->forw->mtu;
  389.     else
  390.         return iface->mtu;
  391. }
  392. #endif
  393. /* Look up target in hash table, matching the entry having the largest number
  394.  * of leading bits in common. Return default route if not found;
  395.  * if default route not set, return NULLROUTE
  396.  */
  397. static struct route *
  398. rt_lookup(target)
  399. int32 target;
  400. {
  401.     register struct route *rp;
  402.     int bits;
  403.     int32 tsave;
  404.     int32 mask;
  405.  
  406.     if(target == Rt_cache.target)
  407.         return Rt_cache.route;
  408.  
  409.     tsave = target;
  410.  
  411.     mask = ~0;    /* All ones */
  412.     for(bits = 31;bits >= 0; bits--){
  413.         target &= mask;
  414.         for(rp = Routes[bits][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  415.             if(rp->target == target){
  416.                 /* Stash in cache and return */
  417.                 Rt_cache.target = tsave;
  418.                 Rt_cache.route = rp;
  419.                 return rp;
  420.             }
  421.         }
  422.         mask <<= 1;
  423.     }
  424.     if(R_default.iface != NULLIF){
  425.         Rt_cache.target = tsave;
  426.         Rt_cache.route = &R_default;
  427.         return &R_default;
  428.     } else
  429.         return NULLROUTE;
  430. }
  431. /* Convert IP header in host format to network mbuf */
  432. struct mbuf *
  433. htonip(ip,data)
  434. struct ip *ip;
  435. struct mbuf *data;
  436. {
  437.     int16 hdr_len;
  438.     struct mbuf *bp;
  439.     register char *cp;
  440.     int16 checksum;
  441.     int16 fl_offs;
  442.  
  443.     hdr_len = IPLEN + ip->optlen;
  444.     if((bp = pushdown(data,hdr_len)) == NULLBUF){
  445.         free_p(data);
  446.         return NULLBUF;
  447.     }
  448.     cp = bp->data;
  449.     
  450.     *cp++ = (IPVERSION << 4) | (hdr_len >> 2);
  451.     *cp++ = ip->tos;
  452.     cp = put16(cp,ip->length);
  453.     cp = put16(cp,ip->id);
  454.     fl_offs = ip->offset >> 3;
  455.     if(ip->flags.df)
  456.         fl_offs |= 0x4000;
  457.     if(ip->flags.mf)
  458.         fl_offs |= 0x2000;
  459.  
  460.     cp = put16(cp,fl_offs);
  461.     *cp++ = ip->ttl;
  462.     *cp++ = ip->protocol;
  463.     cp = put16(cp,0);    /* Clear checksum */
  464.     cp = put32(cp,ip->source);
  465.     cp = put32(cp,ip->dest);
  466.     if(ip->optlen != 0)
  467.         memcpy(cp,ip->options,ip->optlen);
  468.  
  469.     /* Compute checksum and insert into header */
  470.     checksum = cksum(NULLHEADER,bp,hdr_len);
  471.     put16(&bp->data[10],checksum);
  472.  
  473.     return bp;
  474. }
  475. /* Extract an IP header from mbuf */
  476. int
  477. ntohip(ip,bpp)
  478. struct ip *ip;
  479. struct mbuf **bpp;
  480. {
  481.     int16 ihl;
  482.     int16 fl_offs;
  483.     char ipbuf[IPLEN];
  484.  
  485.     if(pullup(bpp,ipbuf,IPLEN) != IPLEN)
  486.         return -1;
  487.  
  488.     ip->version = (ipbuf[0] >> 4) & 0xf;
  489.     ip->tos = ipbuf[1];
  490.     ip->length = get16(&ipbuf[2]);
  491.     ip->id = get16(&ipbuf[4]);
  492.     fl_offs = get16(&ipbuf[6]);
  493.     ip->offset = (fl_offs & 0x1fff) << 3;
  494.     ip->flags.mf = (fl_offs & 0x2000) ? 1 : 0;
  495.     ip->flags.df = (fl_offs & 0x4000) ? 1 : 0;
  496.     ip->ttl = ipbuf[8];
  497.     ip->protocol = ipbuf[9];
  498.     ip->source = get32(&ipbuf[12]);
  499.     ip->dest = get32(&ipbuf[16]);
  500.  
  501.     ihl = (ipbuf[0] & 0xf) << 2;
  502.     if(ihl < IPLEN){
  503.         /* Bogus packet; header is too short */
  504.         return -1;
  505.     }
  506.     ip->optlen = ihl - IPLEN;
  507.     if(ip->optlen != 0)
  508.         pullup(bpp,ip->options,ip->optlen);
  509.  
  510.     return ip->optlen + IPLEN;
  511. }
  512. /* Perform end-around-carry adjustment */
  513. int16
  514. eac(sum)
  515. register int32 sum;    /* Carries in high order 16 bits */
  516. {
  517.     register int16 csum;
  518.  
  519.     while((csum = sum >> 16) != 0)
  520.         sum = csum + (sum & 0xffffL);
  521.     return (int16) (sum & 0xffffl);    /* Chops to 16 bits */
  522. }
  523. /* Checksum a mbuf chain, with optional pseudo-header */
  524. int16
  525. cksum(ph,m,len)
  526. struct pseudo_header *ph;
  527. register struct mbuf *m;
  528. int16 len;
  529. {
  530.     register unsigned int cnt, total;
  531.     register int32 sum, csum;
  532.     register char *up;
  533.     int16 csum1;
  534.     int swap = 0;
  535.  
  536.     sum = 0l;
  537.  
  538.     /* Sum pseudo-header, if present */
  539.     if(ph != NULLHEADER){
  540.         sum = hiword(ph->source);
  541.         sum += loword(ph->source);
  542.         sum += hiword(ph->dest);
  543.         sum += loword(ph->dest);
  544.         sum += uchar(ph->protocol);
  545.         sum += ph->length;
  546.     }
  547.     /* Now do each mbuf on the chain */
  548.     for(total = 0; m != NULLBUF && total < len; m = m->next) {
  549.         cnt = min(m->cnt, len - total);
  550.         up = (char *)m->data;
  551.         csum = 0;
  552.  
  553.         if(((long)up) & 1){
  554.             /* Handle odd leading byte */
  555.             if(swap)
  556.                 csum = uchar(*up++);
  557.             else
  558.                 csum = (int16)(uchar(*up++) << 8);
  559.             cnt--;
  560.             swap = !swap;
  561.         }
  562.         if(cnt > 1){
  563.             /* Have the primitive checksumming routine do most of
  564.              * the work. At this point, up is guaranteed to be on
  565.              * a short boundary
  566.              */
  567.             csum1 = lcsum((unsigned short *)up, cnt >> 1);
  568.             if(swap)
  569.                 csum1 = (csum1 << 8) | (csum1 >> 8);
  570.             csum += csum1;
  571.         }
  572.         /* Handle odd trailing byte */
  573.         if(cnt & 1){
  574.             if(swap)
  575.                 csum += uchar(up[--cnt]);
  576.             else
  577.                 csum += (int16)(uchar(up[--cnt]) << 8);
  578.             swap = !swap;
  579.         }
  580.         sum += csum;
  581.         total += m->cnt;
  582.     }
  583.     /* Do final end-around carry, complement and return */
  584.     return ~eac(sum) & 0xffff;
  585. }
  586.